package org.fhkoeln.sgdm.sudoku.logic;

import org.fhkoeln.sgdm.sudoku.Starter;

public class SimpleBacktracker
{
	int curX = -1;
	int curY = 0;
	
	SudokuField data = null;
	
	boolean quit = false;
	boolean successful = false;
	
	public SudokuField backTrack(SudokuField dataSource)
	{
		this.data = dataSource;
		
		selectNextField();
		
		data.values[curY][curX] = 1;
		
		quit = false;
		successful = false;
		
		while(!quit)
		{
			if(isSudokuOk())
			{
				if(isFinished())
				{
					Starter.error("Sudoku solved successful!");
					return data;
				}
				selectNextField();
				
				if(curX >= 9 || curY >= 9)
				{
					Starter.error("Error in SelectNextField!!! Or Sudoku not possible! Exit!");
					quit = true;
					return null;
				}
				
				data.values[curY][curX] = 1;
			}
			else
			{
				sudokuNotOkay();
			}
		}
		return null;
	}
	
	private void sudokuNotOkay()
	{
		if(curX < 0 || curY < 0)
		{
			Starter.error("Sudoku is not solveable!");
			quit = true;
			return;
		}
		
		data.values[curY][curX] ++;
		//Check if we can still decrement the current field
		if(data.values[curY][curX] > 9)
		{
			data.values[curY][curX] = 0;
			selectPrevField();
			sudokuNotOkay();
		}
	}
	
	void selectNextField()
	{
		int fromX = curX + 1;
		for(int j = curY; j < 9; j ++)
		{
			for(int i = fromX; i < 9; i ++)
			{
				if(data.fixed[j][i] == false)
				{
					curX = i;
					curY = j;
					return;
				}
			}
			fromX = 0;
		}
		
		//end of sudoku!
		curX = 9;
		curY = 9;
	}
	
	void selectPrevField()
	{
		int fromX = curX - 1;
		for(int j = curY; j >= 0; j --)
		{
			for(int i = fromX; i >= 0; i --)
			{
				if(data.fixed[j][i] == false)
				{
					curX = i;
					curY = j;
					return;
				}
			}
			fromX = 8;
		}
		
		//end of sudoku
		curX = -1;
		curY = -1;
	}
	
	boolean isSudokuOk()
	{
		
		boolean[] emptyLine = null;
		
		//Check all lines:
		for(int j = 0; j < 9; j++)
		{
			emptyLine = getEmptyLine();
			for(int i = 0; i < 9; i ++)
			{
				if(data.values[j][i] > 0)
				{
					//if the value is already set to true the sudoku is not correct!
					if(emptyLine[data.values[j][i]-1] == true)
					{
						Starter.debug("Found dupe in line: " + j + " at column: " + i);
						Starter.debug(data.toString());
						return false;
					}
					else
					{
						emptyLine[data.values[j][i]-1] = true;
					}
				}
			}
		}
		
		//Check all columns:
		for(int i = 0; i < 9; i++)
		{
			emptyLine = getEmptyLine();
			for(int j = 0; j < 9; j ++)
			{
				if(data.values[j][i] > 0)
				{
					//if the value is already set to true the sudoku is not correct!
					if(emptyLine[data.values[j][i]-1] == true)
					{
						Starter.debug("Found dupe in line: " + j + " at column: " + i);
						Starter.debug(data.toString());
						return false;
					}
					else
					{
						emptyLine[data.values[j][i]-1] = true;
					}
				}
			}
		}
		
		//Check the 9 rects:
		int curRectX = 0;
		int curRectY = 0;
		while(curRectY < 9)
		{
			emptyLine = getEmptyLine();
			for(int j = curRectY; j < curRectY + 3; j ++)
			{
				for(int i = curRectX; i < curRectX + 3; i ++)
				{
					if(data.values[j][i] > 0)
					{
						if(emptyLine[data.values[j][i]-1] == true)
						{
							Starter.debug("Found dupe in line: " + j + " at column: " + i);
							Starter.debug(data.toString());
							return false;
						}
						else
						{
							emptyLine[data.values[j][i]-1] = true;
						}
					}
				}
			}
			
			curRectX += 3;
			if(curRectX == 9)
			{
				curRectX = 0;
				curRectY += 3;
			}
		}
		
		
		return true;
	}
	
	private boolean isFinished()
	{
		if(isSudokuOk())
		{
			for(int j = 0; j < 9; j ++)
			{
				for(int i = 0; i < 9; i ++)
				{
					if(data.values[j][i] == 0)
					{
						return false;
					}
				}
			}
		}
		else
		{
			return false;
		}
		
		return true;
	}
	
	boolean[] getEmptyLine()
	{
		boolean[] newLine = new boolean[9];
		for(int i = 0; i < 9; i ++)
		{
			newLine[i] = false;
		}
		return newLine;
	}
}
